4.1 Merkezilik (Centrality)

Merkezlik, düğümlere giren / çıkan kenarların sayısını tanımlar. Yüksek merkeziyetli ağlarda birçok bağlantıya sahip birkaç düğüm bulunur, düşük merkeziyetli ağlarda benzer sayıda kenara sahip birçok düğüm bulunur.

Tüm ağ için, merkezliliği, köşelerin derece (centr_degree()), yakınlığı (centr_clo()) veya özvektör merkeziliği (centr_eigen()) ile hesaplayabiliriz.

# derece ile merkezilik
centr_degree(union_graph_undir, mode = "total")$centralization

[1] 0.04282795

# yakinlik ile merkezilik
centr_clo(union_graph_undir, mode = "total")$centralization

[1] 0.01414082

# özvektörle merkezilik
centr_eigen(union_graph_undir, directed = FALSE)$centralization

[1] 0.8787532

4.2 Düğüm Derecesi

Düğüm derecesi (node degree) veya derece merkeziliği (degree centrality), bir düğümün ağda ne kadar merkezi olduğunu (yani, kaç tane giriş ve çıkış kenarı olduğunu veya bir kenar üzerinden doğrudan kaç tane diğer düğüme bağlı olduğunu) tanımlar.

union_graph_undir_degree <- igraph::degree(union_graph_undir, mode = "total")

# dügüm sayisina göre standardize etme
union_graph_undir_degree_std <- union_graph_undir_degree/(vcount(union_graph_undir) - 
    1)


node_degree <- tibble::rownames_to_column(as.data.frame(cbind(union_graph_undir_degree)))

node_degree_std <- tibble::rownames_to_column(as.data.frame(cbind(union_graph_undir_degree_std)))

node_degree %>% inner_join(node_degree_std, by = "rowname") %>% rename(degree = union_graph_undir_degree, 
    degree_std = union_graph_undir_degree_std) %>% arrange(desc(degree)) %>% top_n(10)

           rowname degree degree_std
1  Quellon Greyjoy     12 0.05797101
2      Walder Frey     10 0.04830918
3   Oberyn Martell     10 0.04830918
4     Eddard Stark      9 0.04347826
5    Catelyn Stark      8 0.03864734
6       Emmon Frey      7 0.03381643
7  Genna Lannister      7 0.03381643
8     Merrett Frey      7 0.03381643
9    Balon Greyjoy      7 0.03381643
10 Jason Lannister      7 0.03381643
11    Lyarra Stark      7 0.03381643
12   Rickard Stark      7 0.03381643
13     Mace Tyrell      7 0.03381643

Bu durumda düğüm derecesi, bir karakterin kaç çocuğu ve eşi olduğunu yansıtır. 3 karısı ve birkaç çocuğu olan Quellon Greyjoy, Theon ve Asha / Yara’nın büyükbabası zirveye çıkıyor (elbette, Walder Frey’in tüm yavrularını ve eşlerini dahil etseydik, kolayca zirvede olacaktı ama ağ sonsuza kadar artacaktı. daha kafa karıştırıcı olurdu).

4.3 Yakınlık (Closeness)

Bir düğümün yakınlığı, diğer tüm düğümlere olan mesafesini tanımlar. En yüksek yakınlığa sahip bir düğüm daha merkezidir ve bilgiyi diğer birçok düğüme yayabilir.

closeness <- igraph::closeness(union_graph_undir, mode = "total")

# dügüm sayisina göre standardize etme
closeness_std <- closeness/(vcount(union_graph_undir) - 1)

node_closeness <- tibble::rownames_to_column(as.data.frame(cbind(closeness)))

node_closeness_std <- tibble::rownames_to_column(as.data.frame(cbind(closeness_std)))

node_closeness %>% inner_join(node_closeness_std, by = "rowname") %>% rename(closeness = closeness, 
    closeness_std = closeness_std) %>% arrange(desc(closeness)) %>% top_n(10)

            rowname    closeness closeness_std
1       Sansa Stark 0.0002013288  9.726028e-07
2  Tyrion Lannister 0.0002012882  9.724070e-07
3   Tywin Lannister 0.0002011668  9.718201e-07
4  Joanna Lannister 0.0002005616  9.688965e-07
5      Eddard Stark 0.0002002804  9.675381e-07
6     Catelyn Stark 0.0001986492  9.596579e-07
7  Cersei Lannister 0.0001984915  9.588960e-07
8   Jaime Lannister 0.0001975894  9.545382e-07
9    Jeyne Marbrand 0.0001966568  9.500330e-07
10  Tytos Lannister 0.0001966568  9.500330e-07

Game of Thrones’daki çeşitli hikayeleri ve evleri birbirine bağlayan en yakın karakterlerin tümü ana karakterleri çevreliyor.

4.4 Arasındalık Merkeziliği (betweennes centrality)

Arasındalık (betweenness), düğümler arasındaki en kısa yolların sayısını tanımlar. Ara merkezliği yüksek olan düğümler, diğer birçok düğüm arasındaki yoldadır, yani farklı düğüm grupları arasında anahtar bağlantılar veya köprüler olan kişilerdir. Bir sosyal ağda, bu düğümler çok önemli olacaktır çünkü bilgiyi geniş bir erişime sahip insanlara aktarmaları muhtemeldir.

igraph işlevi betweenness(), köşe arasındalığını hesaplar, edge_betweenness() kenar arasındalığını hesaplar.

betweenness <- igraph::betweenness(union_graph_undir, directed = FALSE)

# ikili dügüm sayisina göre standardize etme
betweenness_std <- betweenness/((vcount(union_graph_undir) - 1) * (vcount(union_graph_undir) - 
    2)/2)

node_betweenness <- tibble::rownames_to_column(as.data.frame(cbind(betweenness)))

node_betweenness_std <- tibble::rownames_to_column(as.data.frame(cbind(betweenness_std)))

node_betweenness %>% inner_join(node_betweenness_std, by = "rowname") %>% rename(betweenness = betweenness, 
    betweenness_std = betweenness_std) %>% arrange(desc(betweenness)) %>% top_n(10)

             rowname betweenness betweenness_std
1       Eddard Stark    6926.864       0.3248846
2        Sansa Stark    6165.667       0.2891828
3   Tyrion Lannister    5617.482       0.2634718
4    Tywin Lannister    5070.395       0.2378123
5   Joanna Lannister    4737.524       0.2221999
6  Rhaegar Targaryen    4301.583       0.2017533
7    Margaery Tyrell    4016.417       0.1883784
8           Jon Snow    3558.884       0.1669192
9        Mace Tyrell    3392.500       0.1591154
10   Jason Lannister    3068.500       0.1439191

edge_betweenness <- igraph::edge_betweenness(union_graph_undir, directed = FALSE)

data.frame(edge = attr(E(union_graph_undir), "vnames"), betweenness = edge_betweenness) %>% 
    tibble::rownames_to_column() %>% arrange(-betweenness) %>% .[1:10, ]

   rowname                              edge betweenness
1      160      Sansa Stark|Tyrion Lannister    5604.149
2      207          Sansa Stark|Eddard Stark    4709.852
3      212        Rhaegar Targaryen|Jon Snow    3560.083
4      296       Margaery Tyrell|Mace Tyrell    3465.000
5      213             Eddard Stark|Jon Snow    3163.048
6      131  Jason Lannister|Joanna Lannister    3089.500
7      159 Joanna Lannister|Tyrion Lannister    2983.591
8      171  Tyrion Lannister|Tywin Lannister    2647.224
9      192    Elia Martell|Rhaegar Targaryen    2580.000
10     300         Luthor Tyrell|Mace Tyrell    2565.000

Bu, şimdi aradaki düğüm noktasını tepe noktası.size ve kenar arasını kenar.genişliği olarak plot fonksiyonumuza besleyerek çizim yapabiliriz:

pdf("family_tree_GoT_betweenness.pdf", width = 35, height = 35)
plot(union_graph_undir, layout = layout, vertex.label = gsub(" ", "\n", V(union_graph_undir)$name), 
    vertex.shape = V(union_graph_undir)$shape, vertex.color = V(union_graph_undir)$color, 
    vertex.size = betweenness * 0.001, vertex.frame.color = "gray", vertex.label.color = "black", 
    vertex.label.cex = 0.8, edge.width = edge_betweenness * 0.01, edge.arrow.size = 0.5, 
    edge.color = E(union_graph_undir)$color, edge.lty = E(union_graph_undir)$lty)

legend("topleft", legend = c("Node color:", as.character(color_vertices$house), NA, 
    "Edge color:", as.character(colors_edges$type)), pch = 19, col = c(NA, color_vertices$color, 
    NA, NA, colors_edges$color), pt.cex = 5, cex = 2, bty = "n", ncol = 1)

dev.off()

png 
  2 

Ned Stark, arasındalık skoru en yüksek olan karakterdir. Bu, kendisi ve çocukları (özellikle Sansa ve onun Tyrion ile ayarladığı evlilik) diğer evlerle bağlantı kurduğu ve hikayenin ortaya çıktığı merkezi noktalar olduğu için mantıklı geliyor. Bununla birlikte, burada kimin ağa dahil edilecek kadar önemli (örneğin Stark ataları) ve kimin olmayacağına (örneğin Targaryen ve Frey soyağacı olan tüm karmaşık karmaşa) seçimimizin bu sonucu verdiğini unutmamalıyız.

plot(union_graph_undir, layout = layout, vertex.label = gsub(" ", "\n", V(union_graph_undir)$name), 
    vertex.shape = V(union_graph_undir)$shape, vertex.color = V(union_graph_undir)$color, 
    vertex.size = betweenness * 0.001, vertex.frame.color = "gray", vertex.label.color = "black", 
    vertex.label.cex = 0.8, edge.width = edge_betweenness * 0.01, edge.arrow.size = 0.5, 
    edge.color = E(union_graph_undir)$color, edge.lty = E(union_graph_undir)$lty)

legend("topleft", legend = c("Node color:", as.character(color_vertices$house), NA, 
    "Edge color:", as.character(colors_edges$type)), pch = 19, col = c(NA, color_vertices$color, 
    NA, NA, colors_edges$color), pt.cex = 5, cex = 2, bty = "n", ncol = 1)

4.5 Çap (Diameter)

İki düğüm arasındaki en kısa yolun aksine, en uzun yolu veya çapı da hesaplayabiliriz:

# çap
diameter(union_graph_undir, directed = FALSE)

[1] 21

Ağımızda en uzun yol 21 düğümü birbirine bağlar.

Bunu çizebiliriz:

union_graph_undir_diameter <- union_graph_undir
node_diameter <- get.diameter(union_graph_undir_diameter, directed = FALSE)

V(union_graph_undir_diameter)$color <- scales::alpha(V(union_graph_undir_diameter)$color, 
    alpha = 0.5)
V(union_graph_undir_diameter)$size <- 2
V(union_graph_undir_diameter)[node_diameter]$color <- "red"
V(union_graph_undir_diameter)[node_diameter]$size <- 5

E(union_graph_undir_diameter)$color <- "grey"
E(union_graph_undir_diameter)$width <- 1
E(union_graph_undir_diameter, path = node_diameter)$color <- "red"
E(union_graph_undir_diameter, path = node_diameter)$width <- 5

plot(union_graph_undir_diameter, layout = layout, vertex.label = gsub(" ", "\n", 
    V(union_graph_undir_diameter)$name), vertex.shape = V(union_graph_undir_diameter)$shape, 
    vertex.frame.color = "gray", vertex.label.color = "black", vertex.label.cex = 0.8, 
    edge.arrow.size = 0.5, edge.lty = E(union_graph_undir_diameter)$lty)

legend("topleft", legend = c("Node color:", as.character(color_vertices$house), NA, 
    "Edge color:", as.character(colors_edges$type)), pch = 19, col = c(NA, color_vertices$color, 
    NA, NA, colors_edges$color), pt.cex = 5, cex = 2, bty = "n", ncol = 1)

png 
  2 

4.6 Geçişlilik (Transitivity)

Geçişlilik, bir tepe noktasının bitişik köşelerinin bağlanma olasılığını ölçer. Buna bazen kümeleme katsayısı da denir.

Tüm ağ için geçişliliği veya üçgenlerin bağlı üçlülere oranını hesaplayabiliriz:

transitivity(union_graph_undir, type = "global")

[1] 0.2850679

Veya her bir düğüm için:

transitivity <- data.frame(name = V(union_graph_undir)$name, transitivity = transitivity(union_graph_undir, 
    type = "local")) %>% mutate(name = as.character(name))
union_characters <- left_join(union_characters, transitivity, by = "name")
transitivity %>% arrange(-transitivity) %>% .[1:10, ]

                name transitivity
1       Robert Arryn            1
2   Ormund Baratheon            1
3     Selyse Florent            1
4  Shireen Baratheon            1
5   Amarei Crakehall            1
6       Marissa Frey            1
7        Olyvar Frey            1
8        Perra Royce            1
9        Perwyn Frey            1
10         Tion Frey            1

Bizimki bir aile ağı olduğu için, geçişliliği 1 olan karakterler ebeveynleri veya çocukları ile üçgenler oluşturur.

4.7 PageRank Merkeziliği

PageRank (Google tarafından arama sonuçlarının önemini sıralamak için kullanılır) özvektör merkeziliğine benzer. Özvektör merkeziliği, sahip oldukları yüksek dereceli düğümlere bağlantı sayısına göre bir ağdaki düğümleri puanlar. Bu nedenle, düğüm öneminin bir ölçüsüdür. PageRank, benzer şekilde, çok sayıda gelen kenarları (veya bağlantıları) varsa düğümleri daha önemli kabul eder.

page_rank <- page.rank(union_graph_undir, directed = FALSE)
page_rank_centrality <- data.frame(name = names(page_rank$vector), page_rank = page_rank$vector) %>% 
    mutate(name = as.character(name))
union_characters <- left_join(union_characters, page_rank_centrality, by = "name")
page_rank_centrality %>% arrange(-page_rank) %>% .[1:10, ]

                name   page_rank
1     Oberyn Martell 0.018402407
2    Quellon Greyjoy 0.016128129
3        Walder Frey 0.012956029
4       Eddard Stark 0.011725019
5       Cregan Stark 0.010983561
6      Catelyn Stark 0.010555473
7       Lyarra Stark 0.009876629
8  Aegon V Targaryen 0.009688458
9      Balon Greyjoy 0.009647049
10         Jon Arryn 0.009623742

Oberyn Martell, Quellon Greyjoy ve Walder Frey en yüksek sayıda eşe sahipler, bu nedenle çocuklar ve torunlar PageRank için en yüksek puanı alıyorlar.

4.8 Bir Ağın Matris Gösterimi

Düğümler arasındaki bağlantılar, bitişik(adjency) matris olarak da gösterilebilir. Grafik nesnemizi igraph’ın as_adjacency_matrix() işlevi ile bitişik matrisine dönüştürebiliriz. İki düğüm arasında bir kenar olduğunda, matristeki bu alana 1 atanır, aksi takdirde 0 olur.

adjacency <- as.matrix(as_adjacency_matrix(union_graph_undir))

4.9 Özvektör Merkeziliği

Şimdi bitişik matrisin özdeğerlerini ve özvektörlerini hesaplayabiliriz.

# derece köse matris
degree_diag <- diag(1/igraph::degree(union_graph_undir))

# PageRank matris
pagerank <- adjacency %*% degree_diag
eigenvalues <- eigen(pagerank)

En yüksek öz değere sahip özvektör, çok sayıda egoya sahip olan veya birçok kenarlı köşelere bağlı olan köşeleri yüksek puanlar.

eigenvector <- data.frame(name = rownames(pagerank), eigenvector = as.numeric(eigenvalues$vectors[, 
    which.max(eigenvalues$values)]))

union_characters <- left_join(union_characters, eigenvector, by = "name")

eigenvector %>% arrange(eigenvector) %>% .[1:10, ]

                      name eigenvector
1          Quellon Greyjoy  -0.6625628
2            Balon Greyjoy  -0.3864950
3   Lady of House Sunderly  -0.3312814
4           Alannys Harlaw  -0.2760678
5  Lady of House Stonetree  -0.2208543
6      Asha (Yara) Greyjoy  -0.1656407
7            Robin Greyjoy  -0.1104271
8            Euron Greyjoy  -0.1104271
9          Urrigon Greyjoy  -0.1104271
10       Victarion Greyjoy  -0.1104271

Son derece bağlantılı aile bağları nedeniyle (yani yalnızca bir avuç bağlantı vardır, ancak neredeyse hepsi üçgen şeklindedir), Greyjoy’lar en yüksek özdeğerlerle puanlanmıştır.

Özvektör merkezilik puanlarını şu şekilde bulabiliriz:

eigen_centrality <- igraph::eigen_centrality(union_graph_undir, directed = FALSE)

eigen_centrality <- data.frame(name = names(eigen_centrality$vector), eigen_centrality = eigen_centrality$vector) %>% 
    mutate(name = as.character(name))

union_characters <- left_join(union_characters, eigen_centrality, eigenvector, by = "name")

eigen_centrality %>% arrange(-eigen_centrality) %>% .[1:10, ]

               name eigen_centrality
1   Tywin Lannister        1.0000000
2  Cersei Lannister        0.9168980
3  Joanna Lannister        0.8358122
4   Tytos Lannister        0.8190076
5    Jeyne Marbrand        0.8190076
6   Genna Lannister        0.7788376
7   Jaime Lannister        0.7642870
8  Robert Baratheon        0.7087042
9        Emmon Frey        0.6538709
10      Walder Frey        0.6516021

Özvektör merkeziliğini göz önüne aldığımızda, Tywin ve çekirdek Lannister ailesi en yüksek skora sahiptir.

4.10 En Önemli Karakterler Kimlerdir?

Game of Thrones’ta hangi karakterlerin en önemli olduklarına karar verebilmek için tüm düğüm-düzeyindeki bilgiyi kullanacağız. Bu tür düğüm seviyesi özellikleri, yapay öğrenme algoritmaları için girdi olarak da kullanılabilir.

node_degree <- data.frame(degree = union_graph_undir_degree, degree_std = union_graph_undir_degree_std) %>% 
    tibble::rownames_to_column()

union_characters <- left_join(union_characters, node_degree, by = c(name = "rowname"))

union_characters %>% filter(!is.na(house2)) %>% dplyr::select(-contains("_std")) %>% 
    gather(x, y, degree:eigen_centrality) %>% ggplot(aes(x = name, y = y, color = house2)) + 
    geom_point(size = 3) + facet_grid(x ~ house2, scales = "free") + theme_bw() + 
    theme(axis.text.x = element_text(angle = 45, vjust = 1, hjust = 1))

png 
  2 

Birlikte ele alındığında House Stark (özellikle Ned ve Sansa) ve House Lannister’ın (özellikle Tyrion) Game of Thrones’daki en önemli aile bağlantıları olduğunu söyleyebiliriz.

4.11 Düğüm Grupları

Ayrıca ağımızdaki ikili (iki düğümlü çiftler), üçlüler (üç düğümlü gruplar) ve daha büyük klikleri analiz edebiliriz. Çiftler için igraph’dan dyad_census() veya sna’dan dyad.census() işlevini kullanabiliriz. Her ikisi de aynıdır ve bir Holland ve Leinhardt ikili nüfus sayımını hesaplar.

# igraph::dyad_census(union_graph_undir)
sna::dyad.census(adjacency)

     Mut Asym  Null
[1,] 326    0 21202

Burada:

• mut: Karşılıklı bağlantılı çiftlerin sayısı (bizim durumumuzda eşler).
• asym: Karşılıklı olmayan bağlantıları olan çiftlerin sayısı (orijinal ağda: anne-çocuk ve baba-çocuk ilişkileri; ancak yönlendirilmemiş ağda yok).
• null: Aralarında bağlantı olmayan çiftlerin sayısı.

Benzeri üçlüler için de hesaplanabilir:

# igraph::triad_census(union_graph_undir)
sna::triad.census(adjacency)

         003 012   102 021D 021U 021C 111D 111U 030T 030C 201 120D 120U 120C
[1,] 1412100   0 65261    0    0    0    0    0    0    0 790    0    0    0
     210 300
[1,]   0 105

triad.classify(adjacency, mode = "graph")

[1] 2

Ayrıca belirttiğimiz herhangi bir uzunluktaki yolların ve döngülerin sayısını burada da hesaplayabiliriz, örn. uzunluk <= 5. Kenarlar için, verilen maksimum uzunluğa kadar tüm yollar veya döngüler için sayıların toplamını elde ederiz. Köşeler / düğümler için, her düğümün ait olduğu yolların veya döngülerin sayısını elde ederiz.

node_kpath <- kpath.census(adjacency, maxlen = 5, mode = "graph", tabulate.by.vertex = TRUE, 
    dyadic.tabulation = "sum")
edge_kpath <- kpath.census(adjacency, maxlen = 5, mode = "graph", tabulate.by.vertex = FALSE)
edge_kpath

$path.count
    1     2     3     4     5 
  326  1105  2973  7183 17026 

Bunu çizebiliriz de:

node_kcycle <- kcycle.census(adjacency, maxlen = 8, mode = "graph", tabulate.by.vertex = TRUE, 
    cycle.comembership = "sum")
edge_kcycle <- kcycle.census(adjacency, maxlen = 8, mode = "graph", tabulate.by.vertex = FALSE)
edge_kcycle

$cycle.count
  2   3   4   5   6   7   8 
  0 105 136  27  57  58  86 

node_kcycle_reduced <- node_kcycle$cycle.comemb
node_kcycle_reduced <- node_kcycle_reduced[which(rowSums(node_kcycle_reduced) > 0), 
    which(colSums(node_kcycle_reduced) > 0)]
gplot(node_kcycle_reduced, label.cex = 0.5, vertex.cex = 0.75, displaylabels = TRUE, 
    edge.col = "grey")

png 
  2 

Bu ağdaki en büyük düğüm grubu üçtür, yani tüm ebeveyn / çocuk ilişkileri. Bu nedenle, hepsini çizmek gerçekten mantıklı değil, ancak bunları çizebilir ve renklendirebiliriz:

vcol <- rep("grey80", vcount(union_graph_undir))
# highlight first of largest cliques
vcol[unlist(largest_cliques(union_graph_undir)[[1]])] <- "red"
plot(union_graph_undir, layout = layout, vertex.label = gsub(" ", "\n", V(union_graph_undir)$name), 
    vertex.shape = V(union_graph_undir)$shape, vertex.color = vcol, vertex.size = 5, 
    vertex.frame.color = "gray", vertex.label.color = "black", vertex.label.cex = 0.8, 
    edge.width = 2, edge.arrow.size = 0.5, edge.color = E(union_graph_undir)$color, 
    edge.lty = E(union_graph_undir)$lty)

4.12 Kümeleme

Ayrıca düğüm gruplarını uç aralıklarına göre kümeleyerek ağımızdaki grupları da arayabiliriz:

ceb <- cluster_edge_betweenness(union_graph_undir)
modularity(ceb)

[1] 0.8359884

plot(ceb, union_graph_undir, layout = layout, vertex.label = gsub(" ", "\n", V(union_graph_undir)$name), 
    vertex.shape = V(union_graph_undir)$shape, vertex.size = (V(union_graph_undir)$popularity + 
        0.5) * 5, vertex.frame.color = "gray", vertex.label.color = "black", vertex.label.cex = 0.8)

png 
  2 

Veya çoğaltma etiketlerine göre:

clp <- cluster_label_prop(union_graph_undir)
plot(clp, union_graph_undir, layout = layout, vertex.label = gsub(" ", "\n", V(union_graph_undir)$name), 
    vertex.shape = V(union_graph_undir)$shape, vertex.size = (V(union_graph_undir)$popularity + 
        0.5) * 5, vertex.frame.color = "gray", vertex.label.color = "black", vertex.label.cex = 0.8)

png 
  2